package org.example.myleet.rosalind.edta;

import org.example.myleet.rosalind.utils.FastaReader;
import org.example.myleet.rosalind.utils.FastaSequence;

import java.util.List;

public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String path = solution.getClass().getResource("").getPath() + "example.txt";
        List<FastaSequence> sequences = FastaReader.parseFastaFromFile(path);
        String s = sequences.get(0).getSequence();
        String t = sequences.get(1).getSequence();
        int m = s.length(), n = t.length();
        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; ++i) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[i][0] = i;
        }
        for (int j = 1; j <= n; ++j) {
            //和空字符串都不匹配，编辑距离等于字符串长度
            dp[0][j] = j;
        }
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (s.charAt(i - 1) == t.charAt(j - 1)) {
                    //字符匹配，则无需增加编辑距离
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    //不匹配，则有3种选择
                    //1. 选用dp[i-1][j-1]+1，即s[i-1]和t[j-1]不匹配但通过替换从s变成t上面对应的字符
                    //2. 选用dp[i][j-1]+1，即s[i-1]和t[j-1]不匹配但通过选用s[i]插入、t字符串跳过一个字符匹配（使用"-"表示）
                    //3. 选用dp[i-1][j]+1，即s[i-1]和t[j-1]不匹配但通过选用t[j]插入、s字符串跳过一个字符匹配（使用"-"表示）
                    //从中选一种编辑距离最小的得到dp[i][j]
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        int editDistance = dp[m][n];
        System.out.println(editDistance);
        //然后从dp[m][n]位置通过回溯重新构建利用编辑距离重构alignment
        StringBuilder sp = new StringBuilder(2 * m);
        StringBuilder tp = new StringBuilder(2 * n);
        int row = m, col = n;
        while (row > 0 || col > 0) {
            if (row > 0 && col > 0) {
                if (dp[row - 1][col - 1] < dp[row - 1][col] && dp[row - 1][col - 1] < dp[row][col - 1]) {
                    //dp[row-1][col-1]最小，则可能为s[i-1]和t[j-1]匹配或通过替换得到
                    sp.append(s.charAt(row - 1));
                    tp.append(t.charAt(col - 1));
                    --row;
                    --col;
                } else if (dp[row - 1][col] < dp[row][col - 1] && dp[row - 1][col] < dp[row - 1][col - 1]) {
                    //dp[row-1][col]最小，则可能为s[i-1]作为插入，而t的alignment使用"-"进行align
                    sp.append(s.charAt(row - 1));
                    tp.append('-');
                    --row;
                } else if (dp[row][col - 1] < dp[row - 1][col] && dp[row][col - 1] < dp[row - 1][col - 1]) {
                    //dp[row][col-1]最小，则可能为t[j-1]作为插入，而s的alignment使用"-"进行align
                    sp.append('-');
                    tp.append(t.charAt(col - 1));
                    --col;
                } else  {
                    if (dp[row - 1][col - 1] == dp[row][col] && (dp[row - 1][col - 1] <= dp[row - 1][col] || dp[row - 1][col - 1] <= dp[row][col - 1])) {
                        //dp[row-1][col-1]和dp[row][col]相等，且dp[row-1][col]和dp[row][col-1]都较大，则可能为s[i-1]和t[j-1]匹配或通过替换得到
                        sp.append(s.charAt(row - 1));
                        tp.append(t.charAt(col - 1));
                        --row;
                        --col;
                    } else if (dp[row - 1][col] < dp[row][col - 1]) {
                        //可能为s[i-1]作为插入，而t的alignment使用"-"进行align
                        sp.append(s.charAt(row - 1));
                        tp.append('-');
                        --row;
                    } else {
                        //可能为t[j-1]作为插入，而s的alignment使用"-"进行align
                        sp.append('-');
                        tp.append(t.charAt(col - 1));
                        --col;
                    }
                }
            } else {
                //剩下没有匹配完的则对应使用"-"进行align
                if (row > 0) {
                    sp.append(s.charAt(row - 1));
                    tp.append('-');
                    --row;
                }
                if (col > 0) {
                    sp.append('-');
                    tp.append(t.charAt(col - 1));
                    --col;
                }
            }
        }
        //由于回溯是append的方式拼接的，因此要得到正序的结果需要进行reverse
        sp.reverse();
        tp.reverse();
        System.out.println(sp);
        System.out.println(tp);
    }
}
